對稱密鑰演算法 - RC5

我們看過了非常複雜的DES之後。

我們來看點簡單的（再加上今天出門，太累了）。

RC5

李維斯特密碼 5 - Rivest Cipher 5（RC5）

我們簡單的先看一下圖一：

圖一

RC5可是被稱為很簡潔的對稱式加密之一了。

在圖中並沒有什麼其他的難懂的東西，無非都是XOR、位移、相加。

比較麻煩的是RC5的金鑰擴充，或稱為金鑰生成。

圖片中的步驟很簡單的。
但圖中沒寫到的幾個要件，我先提一下。

1. 加密的話，是兩個字（其長度可以是32、64、128位元）。
2. 金鑰長度可以是0到2040位元
3. 回合次數可以是1到255次。

加密

圖中還少了一個前置步驟，在這邊先提出來。

必須先把字A跟字B跟『金鑰』相加。

加密過程

1. 字A跟金鑰第1部分、字B跟金鑰第2部分相加。
2. 然後把A跟B做XOR後，向左位移B個字元，每一次位移都將把最左邊的字元移到最右邊，做循環移動，再加上金鑰的第3部分，得到新的A。
3. 再把新的A跟B做XOR後，向左移動新A個位元，每一次位移都將把最左邊的字元移到最右邊，做循環移動，再加上金鑰的第4部分，得到新的B。
4. 把2跟3步驟，重複N次。
5. 將資料A跟B回傳。

Python 的範例Code

A = A + S[0]
B = B + S[1]
for i in range(1,n+1):
    A = rotl((A ^ B), B) + S[2 * i]
    B = rotl((B ^ A), A) + S[2 * i + 1]
return A,B

def rotl(num, bits):
    bit = num & (1 << (bits-1))
    num <<= 1
    if(bit):
        num |= 1
    num &= (2**bits-1)

    return num

上述程式碼修改自RC5 WiKi。
rotl 來自 Rot GitHub。

解密

其實就是把這個過程顛倒過來。

解密過程

1. 把B字減掉金鑰的第N部分，向右移動A個位元，每一次位移都將把最右邊的字元移到最左邊，做循環移動，再把A跟做完前述的動作的B做XOR後，得到還原B。
2. 把A字減掉金鑰的第N-1部分，向右移動還原B位元，每一次位移都將把最右邊的字元移到最左邊，做循環移動，再把做完前述的動作的A跟還原B做XOR後，得到還原A。
3. 把2跟3步驟，重複N次。
4. 最終還原B跟金鑰第2部分、最終還原A跟金鑰第1部分相減。
5. 將資料A跟B回傳。

Python 的範例Code

for i in range(n,0,-1):
    B = rotr((B - S[2 * i + 1]), A) ^ A
    A = rotr((A - S[2 * i]), B) ^ B
B = B - S[1]
A = A - S[0]
return A,B

def rotr(num, bits):
    num &= (2**bits-1)
    bit = num & 1
    num >>= 1
    if(bit):
        num |= (1 << (bits-1))

    return num

上述程式碼修改自RC5 WiKi。
rotr 來自 Rot GitHub。

金鑰擴充與生成

這個部分比較複雜，我們一樣慢慢看。

1. 第一個點，就是先設定 一個字的長度(w) 了，可以是16、32、64位元。
2. 然後我們將一個字去除以8，得到一個之後將會用到的參數u。
   • u = w/8
3. 先把傳進來的 金鑰長度(l) 去除以u之後無條件去小數點得到一個c，長度最小要為1。
   • c = ceil(l/u)
4. 做一個空的 臨時金鑰陣列(L[]) ，然後從 金鑰長度(l) - 1到0，將 目前循環的次數(i) 除以u的位子向右8個位元後加入 目前循環的次數(i) 的 金鑰(K) 。
   • i = loop l-1 down to 0
   • L[i/u] = (L[i/u] << 8) + K[i]
5. 然後做一個空的 隨機陣列(S[]) ，這個陣列的第0個資料是『 自然對數(e) - 2後乘2的 一個字的長度(w) 次方，並取奇數』。
   • S[0] = X
   • X = Odd((e-2)*2^w)
     1. w=16 時 X = 0xB7E1
     2. w=32 時 X = 0xB7E15163
     3. w=64 時 X = 0xB7E151628AED2A6B
6. 之後填滿隨機陣列，從1到 加密的輪數(r) +1乘2，其數字是，上一筆數字加上『 黃金比率(Φ) - 1乘2的 一個字的長度(w) 的次方，並取奇數』。
   • i = loop 1 to 2*(r+1)
   • S[i] = X
   • X = Odd((Φ-2)*2^w)
     1. w=16 時 X = 0x9E37
     2. w=32 時 X = 0x9E3779B9
     3. w=64 時 X = 0x9E3779B97F4A7C15
7. 將接下來的步驟重複3乘『 金鑰有多少字(c) 或 加密輪數(r) + 1乘2，取最大的那個』。
   • Loop 3*max(c,2*(r+1)) time
8. 設定A＝B＝i=j＝0。
   • A＝B＝i=j＝0
9. A會等於 隨機陣列第i筆(S[i]) ，而每一次做『 隨機陣列第i筆(S[i]) + A + B後，向左3位元，每一次位移都將把最左邊的字元移到最右邊，做循環移動』。
   • A = S[i] = (S[i] + A + B) <<< 3
10. B會等於臨時金鑰陣列第j筆(L[j])，而每一次做『臨時金鑰陣列第j筆(L[j]) + A + B 後，向左 A + B 位元，每一次位移都將把最左邊的字元移到最右邊，做循環移動』。
    • B = L[j] = (L[j] + A + B) <<< (A + B)
11. i為『i加1取 加密的輪數(r) + 1乘2 餘數』。
    • i = (i + 1) % 2*(r+1)
12. j為『j加1取 金鑰有多少字(c) 餘數』。
    • j = (j + 1) % c
13. 完成7的循環後將S輸出為金鑰。
    • return S

上述程式碼修改必解析自RC5 WiKi。

RC5 結論

能看到其實RC5的加解密十分的漂亮，同時也做到很好的混淆。

RC6原本也是AES的候選之一，而RC6跟RC5差別只在於『加密的字』。

RC6可加密的字從2個變成了4個。

而核心的流程依然不變。

金鑰的生產或擴充比較複雜，其他的地方其實還不算太難。

但有注意到一件事，這個算法用到了『+』，也算是位移的一種，很多算法不用+其實就是怕溢位的問題就是了。

然後金鑰的生成也是很多數學的公式在裡面，不單單只是列表、對照、位移。

今天寫的東西不多，但依然介紹了整體的流程，同時也是很好把程式碼實現的。

RC5也是很安全的，提供的加密字元也能到256位元。

雖然看起來只有兩字，但一個字元最高可以支援到128位元。

參考資料

RC5 WiKi

Rot GitHub